Subroutines
Frequently, a software program depends upon a subroutine in order to perform one or more operations. For example, a spreadsheet program may depend upon a “multiply” subroutine to multiply spreadsheet entries and/or depend upon an “add” subroutine to add spreadsheet entries. Typically, a subroutine: 1) accepts one or more existing variables as inputs; 2) performs its function in light of these inputs; and 3) returns one or more output values (i.e., responds with the result(s) of the subroutine function).
A subroutine is “called” upon (also referred to as a “function call”) by another routine when needed. Thus, a subroutine may also be referred to as a called routine. The routine that calls the subroutine may be referred to as a caller routine. Each subroutine typically has a unique name. Thus, for example, a statement “CALL foo(x,y)” within a caller routine indicates that a subroutine named “foo” is being called. A subroutine typically accepts its input values when it is called. After the subroutine has finished its operation, it presents its output back to the caller routine. This activity may be referred to as a “return” or “function return”.
The manner in which a program uses its subroutines may be expressed in a call graph, an example of which is shown in FIG. 1. A call graph represents the flow of a program as a network 100 where routines are represented as network nodes. For example, as seen in FIG. 1, routines named “foo(x,y)”, “bar(x,y)”, “foobar(x,y)”, and “main(x,y)” exist at nodes 101, 102, 103, and 104 respectively.
An arrow into a routine represents the start of operation for the particular routine. Thus, an arrow into a subroutine (e.g., arrow 151) represents a function call of the subroutine and an arrow from a subroutine (e.g., arrow 152) represents a return by the subroutine. Note that as mentioned above a subroutine may depend upon and call another subroutine. Thus, as seen in FIG. 1, subroutine “bar(x,y)” 102 calls upon subroutine “foobar(x,y)” 103 as represented by arrow 153.
Control Flow Graph Representation of a Routine
Referring to FIG. 2, a “control flow graph” breaks down a routine into a network 200 of basic blocks where the network reflects the overall flow of the routine. Basic blocks 201 through 208 are represented as nodes within the control graph 200 example shown in FIG. 2. A basic block is a collection of processor instructions (that are typically ordered in series according to the sequence in which they will be executed).
When the instructions within a basic block are executed, the routine effectively progresses through a portion of its function. For example, while the instructions of basic block 207 are being executed, the program may be performing a calculation or making some form of determination. The flow of the routine is accomplished by effectively “hopping” from node to node (i.e., basic block to basic block) according to the directions provided by the control graph.
Typically, a basic block terminates with or a “program branch” type or instruction. Thus, each basic block typically represents a collection of instructions that are executed until a “branch” is reached in the program. For simplicity, function calls and function returns for a subroutine are not represented as branch statements in this description, although they may be viewed as such in actual practice.
When the program reaches a “branch”, the basic block terminates and the program “jumps” to the next basic block pointed to by the control flow graph. The next basic block represents the next portion of instructions that the program executes as a result of the branch. In this manner, the processor executes instructions in the sequence mandated by the subroutine's control flow graph.